package com.zzy.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class Q30_MergeSort {

    public static int[] nums = new int[]{5,7,1,2,8,9,3};

    public static void main(String[] args) {
//        int[] ints = Arrays.copyOfRange(nums, 0, 3);
//        int[] ints1 = Arrays.copyOfRange(nums, 3, nums.length);
//        System.out.println(ints);
//        int[] n = new int[0];
//        System.out.println(n == null);
        int[] result = mergeSort(nums);
        for(int x : result){
            System.out.println(x);
        }
    }

    private static int[] mergeSort(int[] nums){
        if(nums.length < 2){
            return nums;
        }
        int len = nums.length;
        int mid = len / 2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, len);
        return merge(mergeSort(left),mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int p1 = 0;
        int p2 = 0;
        for(int i = 0 ; i < result.length;i++){
            if(p1 > left.length - 1){
                result[i] = right[p2++];
            } else if(p2 > right.length - 1){
                result[i] = left[p1++];
            } else if(left[p1] > right[p2]){
                result[i] = right[p2++];
            } else {
                result[i] = left[p1++];
            }
        }
        return result;
    }


//    private static int[] mergeSort(int[] nums){
//        if(nums.length < 2){
//            return nums;
//        }
//        int mid = nums.length / 2;
//        int[] left = Arrays.copyOfRange(nums, 0, mid);
//        int[] right = Arrays.copyOfRange(nums, mid, nums.length);
//        return merge(mergeSort(left),mergeSort(right));
//    }
//
//    private static int[] merge(int[] left, int[] right) {
//        int[] result = new int[left.length + right.length];
//        int m = 0;
//        int n = 0;
//        for(int i = 0 ; i < result.length;i++){
//            if(m > left.length - 1){
//                result[i] = right[n++];
//            }else if(n > right.length - 1){
//                result[i] =  left[m++];
//            } else if(left[m] > right[n]){
//                result[i] = right[n++];
//            } else{
//                result[i] = left[m++];
//            }
//        }
//        return result;
//
//    }

}
